from typing import List


class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        size = len(nums)

        # 计算前缀和
        prefix = [0] * (size + 1)
        for i in range(size):
            prefix[i + 1] = prefix[i] + nums[i]
        # print("前缀和:", prefix)

        # 定义状态矩阵
        # dp[i][0] = [在第i个之前已找到1个子数组的最大值,取得最大值时[第1个子数组的索引]]
        # dp[i][1] = [在第i个之前已找到2个子数组的最大值,取得最大值时[第1个子数组的索引,第2个子数组的索引]]
        # dp[i][2] = [在第i个之前已找到3个子数组的最大值,取得最大值时[第1个子数组的索引,第2个子数组的索引,第3个子数组的索引]]
        dp = [[[0, tuple()], [0, tuple()], [0, tuple()]] for _ in range(size + 1)]

        for i in range(size + 1):
            # 从dp[i-1]转移
            if i > 0:
                for j in range(0, 3):
                    if (dp[i - 1][j][0] > dp[i][j][0] or
                            (dp[i - 1][j][0] == dp[i][j][0] and dp[i - 1][j][1] < dp[i][j][1])):
                        dp[i][j] = dp[i - 1][j]

            if i + k <= size:
                # 向dp[i+k]转移第1个子数组
                val = prefix[i + k] - prefix[i]
                idx = (i,)
                if val > dp[i + k][0][0] or (val == dp[i + k][0][0] and idx < dp[i + k][0][1]):
                    dp[i + k][0] = [val, idx]

                # 向dp[i+k]转移第2个子数组
                val = dp[i][0][0] + (prefix[i + k] - prefix[i])
                idx = dp[i][0][1] + (i,)
                if val > dp[i + k][1][0] or (val == dp[i + k][1][0] and idx < dp[i + k][1][1]):
                    dp[i + k][1] = [val, idx]

                # 向dp[i+k]转移第3个子数组
                val = dp[i][1][0] + (prefix[i + k] - prefix[i])
                idx = dp[i][1][1] + (i,)
                if val > dp[i + k][2][0] or (val == dp[i + k][2][0] and idx < dp[i + k][2][1]):
                    dp[i + k][2] = [val, idx]

            # print(i, ":", dp[i])

        return list(dp[-1][2][1])


if __name__ == "__main__":
    print(Solution().maxSumOfThreeSubarrays([1, 2, 1, 2, 6, 7, 5, 1], 2))  # [0, 3, 5]

    # 测试用例36/43
    print(Solution().maxSumOfThreeSubarrays([7, 13, 20, 19, 19, 2, 10, 1, 1, 19], 3))  # [1, 4, 7]
